package com.example.leetcode.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhuhaitao
 * @email zhuhaitao@imoran.net
 * @date 2020/10/12 6:00 下午
 */
public class Solution872 {

    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        aftOrder(root1, list1);
        aftOrder(root2, list2);
        if (list1.size() != list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (!list1.get(i).equals(list2.get(i))) {
                return false;
            }
        }
        return true;
    }

    public static List aftOrder(TreeNode root, List<Integer> list) {
        if (null == root) {
            return list;
        }
        if (null != root.left) {
            aftOrder(root.left, list);
        }
        if (null != root.right) {
            aftOrder(root.right, list);
        }
        if (null == root.left && null == root.right) {
            list.add(root.val);
        }
        return list;
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode rl1 = new TreeNode(2);
        TreeNode rr1 = new TreeNode(3);
        root1.left = rl1;
        root1.right = rr1;

        TreeNode root2 = new TreeNode(1);
        TreeNode rl2 = new TreeNode(2);
        TreeNode rr2 = new TreeNode(3);
        root2.left = rl2;
        root2.right = rr2;

        System.out.println(leafSimilar(root1, root2));
    }
}
